package com.stefan.linkedlist;

//双向链表 头尾插法
public class StefanDoubleLinkedList<E> {
    private int size;
    private Node<E> head;
    private Node<E> tail;

    public StefanDoubleLinkedList() {
        size = 0;
        this.head = null;
        this.tail = null;
    }

    static class Node<E> {
        private E data;
        private Node<E> next;
        private Node<E> prev;

        public Node (E data) {
            this.data = data;
        }
    }

    //尾插法
    public void append (E data) {
        Node<E> node = new Node<>(data);
        if (tail == null) { // 说明这是个空的链表，head必然也是null
            //初始化
            head = node;
        } else {
            tail.next  = node;
            node.prev = tail;
        }
        tail = node;
        size++;
    }
    //头插法
    public void add (E data) {
        Node<E> node = new Node<>(data);
        if (head == null) { // 说明这是个空的链表，tail必然也是null
            //初始化
            tail = node;
        } else {
            head.prev  = node;
            node.next = head;
        }
        head = node;
        size++;
    }

    public boolean remove(E data) {
        if (size == 0) {
            new IndexOutOfBoundsException();
        }
        Node<E> current = head;
        do {
            if (data.equals(current.data)) {
                if (current == head) {
                    head = head.next; //把head.next 设置为head
                    head.prev = null; //然后把当前head（新）的prev设置成空
                } else if (current == tail) {
                    tail = tail.prev;//把前一个设置成tail
                    tail.next = null; //然后把当前tail的next设置成空
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                size--;
                return true;
            }
            current = current.next;
        } while(current !=head);

        return false;
    }

    public static void main(String[] args) {
        StefanDoubleLinkedList<Integer> s = new StefanDoubleLinkedList<>();
        s.append(1);
        s.append(2);
        s.append(3);
        s.append(4);
        s.append(5);
        s.add(6);
        System.out.println("=====");
        s.remove(2);
        System.out.println("====");
        s.remove(6);
        System.out.println("====");
        s.remove(5);
        System.out.println("====");

    }


}
